package com.itheima.leetcode.od.b.binary;

import java.util.Arrays;

/**
 * <h3>爱吃香蕉的珂珂</h3>
 * <p>
 * 题目描述：
 * <p>
 * 孙悟空喜欢吃蟠桃，一天他乘守卫蟠桃园的天兵天将离开了而偷偷的来到王母娘娘的蟠桃园偷吃蟠桃。
 * 已知蟠桃园有 N 棵蟠桃树，第 i 棵蟠桃树上有 N[i]（大于 0）个蟠桃，天兵天将将在 H（不小于蟠桃树棵数）小时后回来。
 * 孙悟空可以决定他吃蟠桃的速度 K（单位：个/小时），每个小时他会选择一颗蟠桃树，从中吃掉 K 个蟠桃，如果这棵树上的蟠桃数小于 K，他将吃掉这棵树上所有蟠桃，然后这一小时内不再吃其余蟠桃树上的蟠桃。
 * 孙悟空喜欢慢慢吃，但仍想在天兵天将回来前将所有蟠桃吃完。
 * 求孙悟空可以在 H 小时内吃掉所有蟠桃的最小速度 K（K 为整数）。
 * <p>
 * 输入描述:
 * <p>
 * 从标准输入中读取两行数字，第一行数字表示每棵数上蟠桃个数，第二行的数字表示天兵天将将离开的时间。
 * <p>
 * 输出描述：
 * <p>
 * 吃掉所有蟠桃的 最小速度 K（K 为整数）或 输入异常时输出 -1。
 * <p>
 * 示例 1：
 * <p>
 * 输入
 * 3 11 6 7
 * <p>
 * 8
 * 输出
 * 4
 * 说明：
 * 天兵天将8个小时后回来，孙悟空吃掉所有蟠桃的最小速度4。
 * <p>
 * 第1小时全部吃完第一棵树，吃3个，
 * 第2小时吃4个，第二棵树剩7个，
 * 第3小时吃4个，第二棵树剩3个，
 * 第4小时吃3个，第二棵树吃完，
 * 第5小时吃4个，第三棵树剩2个，
 * 第6小时吃2个，第三棵树吃完，
 * 第7小时吃4个，第4棵树剩3个，
 * 第8小时吃3个，第4棵树吃完。
 */
public class MinEatingSpeedLeetcode875 {
    public static void main(String[] args) {
        /*Scanner scanner = new Scanner(System.in);

        // 读取香蕉堆数组
        String[] input = scanner.nextLine().split(" ");
        int[] piles = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            piles[i] = Integer.parseInt(input[i]);
        }

        // 读取总时间h
        int h = scanner.nextInt();*/

        int h = 8;

        int[] piles = Arrays.stream("3 11 6 7".split(" ")).mapToInt(Integer::parseInt).toArray();
        // 计算并输出结果
        System.out.println(binarySearch(piles, h));
    }

    /**
     * 二分查找实现
     *
     * @param piles
     * @param h
     * @return
     */
    private static int binarySearch(int[] piles, int h) {
        int left = 1;
        int right = Arrays.stream(piles).max().getAsInt() + 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            long hours = calculateTime(piles, mid);

            if (hours <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }

    /**
     * 计算以给定速度k吃完所有香蕉需要的时间
     *
     * @param piles
     * @param k
     * @return
     */
    private static long calculateTime(int[] piles, int k) {
        long totalHours = 0;
        for (int pile : piles) {
            // 向上取整除法：(pile + k - 1) / k
            totalHours += (pile + k - 1) / k;
        }
        return totalHours;
    }
}